/*****************************************************
Copyright (C) 2020. All rights reserved.
File name     ：HashSep.c
Version       ：v1.0
Author        ：zhengqijun
Date          ：2020-04-03
Function List ：
Description   ：HashTable(separate chaining)
******************************************************/

#include "HashSep.h"
#include <stdlib.h>   // for malloc
#include <stdbool.h>  // for bool
#include <stdio.h>    // for printf
#include "FatalError.h"

#define MinTableSize (10)

// Type Definition
typedef unsigned int Index;
typedef Position List;

struct ListNode {
    ElementType Element;
    Position    Next;
};

/* List *TheList will be an array of lists, allocated later */
/* The lists use headers (for simplicity), */
/* though this wastes space */
struct HashTbl {
    int   TableSize;
    List *TheLists;
};

// Static Function Lists
static int NextPrime(int N);
static Index Hash(ElementType Key, int TableSize);
static Position FindPrevious(ElementType Key, HashTable H);
static void PrintList(List L);

/* Return next prime; assume N >= MinTableSize */
static int NextPrime(int N) {
    int i;
    bool flag;

    if (N % 2 == 0) {
        N++;
    }

    for ( ; ; N += 2) {
        flag = true;
        for (i = 3; i * i <= N; i += 2) {
            /* Not prime! */
            if (N % i == 0) {
                flag = false;
                break;
            }
        }

        if (flag) {
            return N;
        }
    }
}

/* Hash function for ints */
Index Hash(ElementType Key, int TableSize) {
    return Key % TableSize;
}

HashTable InitializeTable(int TableSize) {
    HashTable H;
    int i;

    if (TableSize < MinTableSize) {
        Error("Table size is too small");
        return NULL;
    }

    /* Allocate table */
    H = (HashTable)malloc(sizeof(struct HashTbl));
    if (H == NULL) {
        FatalError("Out of space!!!");
    }

    H->TableSize = NextPrime(TableSize);

    /* Allocate array of lists */
    H->TheLists = (List *)malloc(sizeof(List) * H->TableSize);
    if (H->TheLists == NULL) {
        FatalError("Out of space!!!");
    }

    /* Allocate list headers */
    for (i = 0; i < H->TableSize; ++i) {
        H->TheLists[i] = (List)malloc(sizeof(struct ListNode));
        if (H->TheLists[i] == NULL) {
            FatalError("Out of space!!!");
        } else {
            H->TheLists[i]->Next = NULL;
        }
    }

    return H;
}

void DestroyTable(HashTable H) {
    int i;

    for (i = 0; i < H->TableSize; ++i) {
        Position P = H->TheLists[i];
        Position Tmp;

        while (P != NULL) {
            Tmp = P->Next;
            free(P);
            P = Tmp;
        }
    }

    free(H->TheLists);
    free(H);
}

Position Find(ElementType Key, HashTable H) {
    Position P;
    List L;

    L = H->TheLists[Hash(Key, H->TableSize)];
    P = L->Next;
    while (P != NULL && P->Element != Key) {
        /* Probably need strcmp!! */
        P = P->Next;
    }

    return P;
}

/* If Key is not found, then Next field of returned */
/* Position is NULL */
/* Assumes a header */
Position FindPrevious(ElementType Key, HashTable H) {
    Position P;

    P = H->TheLists[Hash(Key, H->TableSize)];
    while (P->Next != NULL && P->Next->Element != Key) {
        P = P->Next;
    }

    return P;
}

void Insert(ElementType Key, HashTable H) {
    Position P;
    Position NewCell;
    List L;

    P = Find(Key, H);
    /* Key is not found */
    if (P == NULL) {
        NewCell = (Position)malloc(sizeof(struct ListNode));
        if (NewCell == NULL) {
            FatalError("Out of space!!!");
        } else {
            L = H->TheLists[Hash(Key, H->TableSize)];
            NewCell->Next = L->Next;
            NewCell->Element = Key;  /* Probably need strcpy! */
            L->Next = NewCell;
        }
    }
}

void Delete(ElementType Key, HashTable H) {
    Position P;

    P = Find(Key, H);
    /* Found it! */
    if (P != NULL) {
        Position TmpCell;

        TmpCell = FindPrevious(Key, H);
        TmpCell->Next = P->Next;
        free(P);
    }
}

ElementType Retrieve(Position P) {
    return P->Element;
}

static void PrintList(List L) {
    while (L != NULL) {
        printf("%03d    ", L->Element);
        L = L->Next;
    }
}

void PrintHashTable(HashTable H) {
    int i;

    for (i = 0; i < H->TableSize; ++i) {
        PrintList(H->TheLists[i]);
        printf("\n");
    }
}

// EOF

